\relax 
\ifx\hyper@anchor\@undefined
\global \let \oldcontentsline\contentsline
\gdef \contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global \let \oldnewlabel\newlabel
\gdef \newlabel#1#2{\newlabelxx{#1}#2}
\gdef \newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\let \contentsline\oldcontentsline
\let \newlabel\oldnewlabel}
\else
\global \let \hyper@last\relax 
\fi

\citation{Sut89}
\citation{Car96}
\citation{CHK99}
\citation{GKZ95}
\citation{Sut90}
\citation{BaR96}
\citation{DoW01}
\citation{EES04}
\citation{GoK97}
\citation{AmS96}
\citation{AmS96}
\citation{CFF99}
\citation{Gol00}
\citation{Sut90}
\citation{CHK99}
\citation{EES04}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{3}{section.1}}
\newlabel{sec:intro}{{1}{3}{Introduction\relax }{section.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2}All-on to All-off is Realizable}{3}{section.2}}
\newlabel{sec:allontoalloff}{{2}{3}{All-on to All-off is Realizable\relax }{section.2}{}}
\newlabel{thm:allon}{{2.1}{3}{All-on to All-off is Realizable\relax }{theorem.2.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Induction Proof by Graph Theory}{3}{subsection.2.1}}
\newlabel{ssc:induction}{{2.1}{3}{Induction Proof by Graph Theory\relax }{subsection.2.1}{}}
\citation{DoW01}
\citation{GKZ95}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Algebra proof by Linear Algebra}{4}{subsection.2.2}}
\newlabel{ssc:algebra}{{2.2}{4}{Algebra proof by Linear Algebra\relax }{subsection.2.2}{}}
\newlabel{eq:generaladj}{{1}{4}{Algebra proof by Linear Algebra\relax }{equation.1}{}}
\newlabel{eq:stmatrix}{{3}{4}{Algebra proof by Linear Algebra\relax }{equation.3}{}}
\newlabel{thm:allonb}{{2.2}{4}{Algebra proof by Linear Algebra\relax }{theorem.2.2}{}}
\citation{Ary02}
\newlabel{eq:alloff}{{4}{5}{Algebra proof by Linear Algebra\relax }{equation.4}{}}
\newlabel{para:interpre}{{2.2}{5}{Interpretation of Gaussian elimination on Graph\relax }{section*.2}{}}
\@writefile{toc}{\contentsline {paragraph}{Interpretation of Gaussian elimination on Graph}{5}{section*.2}}
\citation{Sut89}
\citation{Car96}
\citation{GKZ95}
\citation{DoW01}
\citation{Sut89}
\citation{CHK99}
\citation{EES04}
\citation{Sut90}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Historical Review}{6}{subsection.2.3}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Completely Solvable}{6}{section.3}}
\newlabel{sec:compsolve}{{3}{6}{Completely Solvable\relax }{section.3}{}}
\newlabel{thm:null0}{{3.1}{6}{Completely Solvable\relax }{theorem.3.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Grid Graph}{6}{subsection.3.1}}
\citation{BaR96}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces An example of $5\times 5$ grid }}{7}{figure.1}}
\newlabel{fig:grid}{{1}{7}{Grid Graph\relax }{figure.1}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.1.1}$\sigma $-game}{7}{subsubsection.3.1.1}}
\newlabel{sss:open}{{3.1.1}{7}{$\sigma $-game\relax }{subsubsection.3.1.1}{}}
\newlabel{eq:opena}{{5}{7}{$\sigma $-game\relax }{equation.5}{}}
\newlabel{prop:splitx}{{3.2}{7}{$\sigma $-game\relax }{theorem.3.2}{}}
\newlabel{eq:recx}{{6}{7}{$\sigma $-game\relax }{equation.6}{}}
\citation{GKZ95}
\newlabel{def:fib}{{3.3}{8}{$\sigma $-game\relax }{theorem.3.3}{}}
\newlabel{fibeqn}{{7}{8}{$\sigma $-game\relax }{equation.7}{}}
\newlabel{prop:xf}{{3.4}{8}{$\sigma $-game\relax }{theorem.3.4}{}}
\newlabel{lem:samenull}{{3.5}{8}{$\sigma $-game\relax }{theorem.3.5}{}}
\newlabel{lem:fibreq}{{3.6}{8}{$\sigma $-game\relax }{theorem.3.6}{}}
\newlabel{eq:fibreq}{{8}{8}{$\sigma $-game\relax }{equation.8}{}}
\newlabel{lem:chp}{{3.7}{9}{$\sigma $-game\relax }{theorem.3.7}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.1.2}$\sigma ^+$-game}{10}{subsubsection.3.1.2}}
\newlabel{sss:close}{{3.1.2}{10}{$\sigma ^+$-game\relax }{subsubsection.3.1.2}{}}
\newlabel{lem:minpol}{{3.9}{11}{$\sigma ^+$-game\relax }{theorem.3.9}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Several APR Graph Classes }{11}{subsection.3.2}}
\citation{AmS96}
\newlabel{cor:allodd}{{3.12}{12}{Several APR Graph Classes \relax }{theorem.3.12}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.1}Path}{12}{subsubsection.3.2.1}}
\newlabel{sss:path}{{3.2.1}{12}{Path\relax }{subsubsection.3.2.1}{}}
\newlabel{prop:path}{{3.13}{12}{Path\relax }{theorem.3.13}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.2}Spider}{13}{subsubsection.3.2.2}}
\newlabel{sss:spider}{{3.2.2}{13}{Spider\relax }{subsubsection.3.2.2}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.3}Caterpillars}{13}{subsubsection.3.2.3}}
\newlabel{sss:caterpillars}{{3.2.3}{13}{Caterpillars\relax }{subsubsection.3.2.3}{}}
\citation{AmS96}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Caterpillars with all vertices of odd degree}}{14}{figure.2}}
\newlabel{fig:cater}{{2}{14}{Caterpillars\relax }{figure.2}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.4}APR Trees}{14}{subsubsection.3.2.4}}
\newlabel{sss:tree}{{3.2.4}{14}{APR Trees\relax }{subsubsection.3.2.4}{}}
\citation{AmS96}
\citation{GKZ95}
\citation{GoK97}
\citation{Klo01}
\citation{Sut00}
\citation{BaR96}
\citation{BaR96}
\citation{GoK97}
\citation{AmS92}
\citation{AmS96}
\citation{Sut88}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Historical Reviews}{15}{subsection.3.3}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Optimize Problems}{15}{section.4}}
\newlabel{sec:optimize}{{4}{15}{Optimize Problems\relax }{section.4}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Minimize Odd Parity Set}{15}{subsection.4.1}}
\citation{Sut88}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.1}$\mathbf  {NP}$-Complete on General Graph}{16}{subsubsection.4.1.1}}
\newlabel{thm:alloffnpc}{{4.2}{16}{$\NP $-Complete on General Graph\relax }{theorem.4.2}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.2}Minimal Activation Set for Several Graph Classes}{16}{subsubsection.4.1.2}}
\citation{CFF99}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces A component of the graph used to embedded 3-SAT}}{17}{figure.3}}
\newlabel{fig:gadget}{{3}{17}{$\NP $-Complete on General Graph\relax }{figure.3}{}}
\newlabel{eq:oddall}{{9}{17}{Minimal Activation Set for Several Graph Classes\relax }{equation.9}{}}
\@writefile{toc}{\contentsline {paragraph}{Path}{17}{section*.3}}
\@writefile{toc}{\contentsline {paragraph}{Cycle}{17}{section*.4}}
\citation{AmS92}
\citation{Val78}
\citation{VTL82}
\@writefile{toc}{\contentsline {paragraph}{Complete Bipartite Graph}{18}{section*.5}}
\@writefile{toc}{\contentsline {paragraph}{Series-Parallel Graph}{18}{section*.6}}
\newlabel{fig:subfig:s1}{{4(a)}{19}{Subfigure 4(a)\relax }{subfigure.4.1}{}}
\newlabel{sub@fig:subfig:s1}{{(a)}{19}{Subfigure 4(a)\relax }{subfigure.4.1}{}}
\newlabel{fig:subfig:s2}{{4(b)}{19}{Subfigure 4(b)\relax }{subfigure.4.2}{}}
\newlabel{sub@fig:subfig:s2}{{(b)}{19}{Subfigure 4(b)\relax }{subfigure.4.2}{}}
\newlabel{fig:subfig:p}{{4(c)}{19}{Subfigure 4(c)\relax }{subfigure.4.3}{}}
\newlabel{sub@fig:subfig:p}{{(c)}{19}{Subfigure 4(c)\relax }{subfigure.4.3}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Composition operation defined in series-parallel graph}}{19}{figure.4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Series 1 Composition}}}{19}{figure.4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Series 2 Composition}}}{19}{figure.4}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Parallel Composition}}}{19}{figure.4}}
\newlabel{fig:sp}{{4}{19}{Series-Parallel Graph\relax }{figure.4}{}}
\citation{Gol00}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Bounds for Off State}{20}{subsection.4.2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.1}Maximizing Off Switches(MOS)}{20}{subsubsection.4.2.1}}
\newlabel{thm:mos}{{4.8}{21}{Maximizing Off Switches(MOS)\relax }{theorem.4.8}{}}
\citation{ArL96}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Reduction from MAX-3SAT to MOS, connection from variable to clause vertices are not shown}}{22}{figure.5}}
\newlabel{fig:mos}{{5}{22}{Maximizing Off Switches(MOS)\relax }{figure.5}{}}
\@writefile{toc}{\contentsline {paragraph}{Hard Approximation of MOS}{22}{section*.7}}
\citation{Gol00}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.2}Fixed-Parameter Problem}{23}{subsubsection.4.2.2}}
\citation{WaW07}
\citation{WaW07}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.3}Lower Bounds for Tree}{24}{subsubsection.4.2.3}}
\newlabel{sss:lbtree}{{4.2.3}{24}{Lower Bounds for Tree\relax }{subsubsection.4.2.3}{}}
\newlabel{lem:fullcolr}{{4.13}{24}{Lower Bounds for Tree\relax }{theorem.4.13}{}}
\citation{WaW07}
\citation{Sut88}
\citation{CFF99}
\citation{AmS96}
\citation{Daw89}
\citation{CLW04}
\citation{Gol00}
\bibstyle{abbrv}
\bibdata{thesis}
\bibcite{AmS92}{1}
\bibcite{AmS96}{2}
\bibcite{ArL96}{3}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Historical Review}{26}{subsection.4.3}}
\bibcite{Ary02}{4}
\bibcite{BaR96}{5}
\bibcite{Car96}{6}
\bibcite{CLW04}{7}
\bibcite{CFF99}{8}
\bibcite{CHK99}{9}
\bibcite{Daw89}{10}
\bibcite{DoW01}{11}
\bibcite{EES04}{12}
\bibcite{Gol00}{13}
\bibcite{GoK97}{14}
\bibcite{GKZ95}{15}
\bibcite{Klo01}{16}
\bibcite{Sut88}{17}
\bibcite{Sut89}{18}
\bibcite{Sut90}{19}
\bibcite{Sut00}{20}
\bibcite{Val78}{21}
\bibcite{VTL82}{22}
\bibcite{WaW07}{23}
